1. Field of the Invention
The present invention relates generally to methods and apparatuses used either for storing data on magnetic storage media, or for communication through channels, when equalization at the receiver side is performed according to a partial response target. More particularly, it relates to PR channels with concatenated coding for error detection and correction.
2. Description of the Related Art
As can be noted from R. Karabed, P. Siegel, E. Soijanin, xe2x80x9cConstrained Coding for Binary Channels with High Intersymbol Interference,xe2x80x9d IEEE Transaction on Information Theory, vol. IT-45, No. 6, September 1999, pp 1777-1797, imposing certain constraints on modulation codes for partial response (PR) channels increases the minimum free Euclidean distance of the decoding trellis, which consequently improves the Bit-Error-Rate (BER) characteristics. However, this improvement is achieved at the cost of increased complexity in encoding/decoding circuits. For example, the Maximum-Transition-Run (MTR) code constraint increases the minimum squared Euclidean distance from 6 to 10 in an EPR4 channel, producing about 2.2 dB in coding gain. The gain can be further improved (by up to 3.5 dB) by using a modified target and the 16/17 quasi-MTR code. The 16/17 quasi-MTR code allows three (but not four) consecutive transitions, and thus results in 65,546 code words of length 17 that meet the code constraint. Since 65,536 different 16-bit input patterns are to be encoded out of the available 17-bit patterns for this code, the complexity of the encoder/decoder circuits is relatively large.
As a general rule, using nontrivial distance enhancing constraints leads to relatively complicated decoding trellises, and as a consequence, to xe2x80x9cbulkyxe2x80x9d time variant decoding circuits. U.S. Pat. No. 5,497,384 discusses a read/write channel with a time variant decoding trellis. Such a decoding method employs a detector trellis structure, which consists of connected trellises with periodically repeated patterns of nodes and subtrellises, that is, it is a periodic permutation of states. The ending states of one subtrellis must mate with the beginning states of an adjacent subtrellis to generate a detector trellis structure for arbitrarily long sequences. Therefore, the survivor metric and survivor sequence for an ending of a subtrellis will be assigned to the beginning state of the subsequent subtrellis with which it is mated. The mating of the ending states and beginning states ensures that the resulting trellis will contain no distance 2 events, and it is therefore used to increase minimum distance properties and reduce error event length.
Alternative solutions are based on a coded modulation technique using so-called Structured Set Partitions (SSP) of the PR channel. See A. Kuznetsov and M. Umemoto, xe2x80x9cStructured Set Partitions and Multilevel Concatenated Coding for Partial Response Channelsxe2x80x9d, IEEE Transactions on Communications, vol. COM-47, No. 6, June 1999, pp. 856-861. The first proposed scheme of this type combines the List Trellis Detector (LTD), which can be considered as a modified Viterbi Algorithm (VA) that searches for the two best paths in the trellis, and an efficient concatenated coding scheme that uses conventional block codes with different error correction capabilities. The structure is quite flexible and can be applied to different types of PR channels, to set different code lengths and error correction capabilities, and to use well-known algebraic and probabilistic decoders for component codes. This significantly improves the overall signal-to-noise ratio (SNR) performance of the read channel compared to the uncoded PR solutions. For the EPR4 channel using the Lorentzian model with user densities of 2.5 and 3.0, the expected SNR gain is between 1.9 and 2.0 dB compared to the uncoded EPR4 channel, and between 2.7 and 2.8 dB compared to the rate 16/17 (d=0, 6/6) coded EPR4 channel.
U.S. Pat. No. 5,881,071 discusses one read/write channel of this type that may consist of the following three steps: 1) An incoming data sequence is de-multiplexed into two or more subsequences. 2) Each of these subsequences is encoded using a conventional encoder designed for error detection or correction purposes. 3) Finally, the parallel sub-strings in the output of the encoders are converted into the channel media code according to the unique SSP table that partitions output words of the EPR4 channel into special subsets. These subsets are characterized by the spectrum of squared minimal Euclidean distances {d02=4,d12=8,d22=16}. The SSP table is a key element in the approach in U.S. Pat. No. 5,881,071, since in the EPR4 channel the minimal squared Euclidean distance d2 of the 3-level concatenated code satisfies d2xe2x89xa7min{d02D0,d12D1,d22D2}, where D0, D1, and D2 are the minimum Hamming distances of the conventional codes used at stage 2 of the encoding process. For example, if D0=8 (as in the extended binary Golay code), D1=4 (as in the Hamming code), and D2=2 (as in the trivial parity check), then d2xe2x89xa732. The drawback of this SSP based approach is the lack of SSP tables for different types of PR channels, and the complexity of the precoders using Read Only Memory (ROM) to store the SSP table. U.S. Pat. No. 5,881,071 teaches the provision of only one SSP table for an EPR4 channel.
The Soft-Output Viterbi Algorithm (SOVA) is another modified VA that gives the most likely path sequence in the trellis as well as the a posteriori probability for each transmitted bit. Similar a posteriori probabilities (soft outputs) are also given by the BCJR algorithm. Since the SOVA and BCJR operate on a trellis, they can be used for a PR channel. These algorithms can also be combined with a soft decoding scheme for block or convolutional modulation codes. A problem with the above mentioned decoding schemes is that, although the BER of such schemes approaches record high levels, the complexity of the decoding schemes implementation and the time delays involved, raise serious problems and have drawbacks.
The problems and drawbacks of the above mentioned techniques are overcome by utilizing simple, efficient SSP precoders, along with exemplary embodiments of the present invention so that the complexity and time delay of a decoder scheme is minimized or reduced for many types of PR channels. The main task of an exemplary embodiment of this invention is to produce precoders and their corresponding logic schemes, together with a method of using these precoders and their schemes, to generate a media code sequence of symbols for data storage channels, with partial response equalization and a multilevel encoding/modulation scheme. Partial responses are defined by the classical and modified target polynomials, while multilevel encoding/modulation schemes include 1) Structured Set Partitions (SSP), 2) a set of conventional block codes with different error correcting capabilities, and 3) a variety of iterative decoding methods such as the List Trellis Decoder (LTD), the BCJR algorithm, and soft decoding of low-density parity check codes. Precoders are derived from the SSP""s, and combined with ECC encoders that are designed for error detection, or error correction, or both. A cascade of parallel ECC encoders followed by an SSP precoder, increases the minimum Euclidean distance between different media code sequences of symbols, and as a result gives lower bit error rates after decoding.